package bloomfilter;

import bitset.MyBitSet;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

class SimpleHash {

    public int cap;//容量
    public int seed;//随机

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    /**
     * 根据seed的不同，创建不同点哈希函数
     * @param key
     * @return
     */
    int hash(String key) {
        int h;
        return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }

}
public class MyBloomFilter {
    //bitSet的初始化大小
    public static final int DEFAULT_SIZE = 1 << 20;
    //位图
    public BitSet bitSet;
    //记录存储的数据数量
    public int usedSize;

    public static final int[] seeds = {3,5,12,6,24,32};

    public SimpleHash[] simpleHashes;

    public MyBloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        //创建哈希函数
        simpleHashes = new SimpleHash[seeds.length];
        for(int i = 0; i < simpleHashes.length; i++) {
            simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器
     * @param val
     */
    public void add(String val) {
        //让每个哈希函数分别处理当前数据，并存入位图中
        for(int i = 0; i < simpleHashes.length; i++) {
            bitSet.set(simpleHashes[i].hash(val));
        }
    }

    /**
     * 是否包含val,这里会存在一定的误判
     * @param val 一定是通过这几个哈希函数看对应的位置
     * @return
     */
    public boolean contains(String val) {
        //只要有1个为0 那么一定不存在
        for(int i = 0; i < simpleHashes.length; i++) {
            if(!bitSet.get(simpleHashes[i].hash(val))) {
                return false;
            }
        }
        return true;
    }

    //测试
    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("hello");
        myBloomFilter.add("hello2");
        myBloomFilter.add("hello3");
        myBloomFilter.add("hehe");
        myBloomFilter.add("haha");
        System.out.println(myBloomFilter.contains("hello4"));
    }
}
